package com.fengye.algorithms.huawei;

import java.util.*;

/**
 * https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=
 * @Author fengye
 * @Date 2023/2/25 11:14
 **/
public class MazeMain {
    public static void main(String[] args) {
        MazeMain maze = new MazeMain();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int m = in.nextInt();
            // 构建地图
            int[][] map = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = in.nextInt();
                }
            }

            maze.bfs(map, n, m);
            maze.depthFirst(map,n,m);
        }

    }

    public void bfs(int[][] map, int n, int m) {
        // 是否访问标记
        int[][] visited = new int[n][m];
        // 方向：向下，向右，向上，向左
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};

        Node start = new Node(0, 0);
        Node end = new Node(n-1,m-1);
        // 利用队列的先进先出特性，存放走到的点
        Queue<Node> queue = new LinkedList<Node>();
        // 存放遍历过的点
        List<Node> list = new ArrayList<>();
        // 先把start加入
        queue.offer(start);
        visited[start.x][start.y] = 1;
        while (!queue.isEmpty()) {
            // 出队
            Node now = queue.poll();
            list.add(now);
            // 已经走到end结束
            if(now.x == end.x && now.y == end.y) {
                break;
            }
            //按各个方向走一下
            for(int i=0;i< dir.length;i++) {
                // 按方向走一步
                Node next = new Node(now.x + dir[i][0], now.y + dir[i][1]);
                if((next.x>=0&&next.x<n) && (next.y>=0&&next.y<m) && map[next.x][next.y]==0 && visited[next.x][next.y]==0) {
                    queue.offer(next);
                    // 标记已经走过
                    visited[next.x][next.y] = 1;
                    // 记录前一步节点
                    next.prex = now.x;
                    next.prey = now.y;
                }
            }
        }
        // stack记录从end到start的过程节点，利用栈的后进先出特性
        Stack<Integer> stack = new Stack<>();
        int px = list.get(list.size()-1).x;
        int py = list.get(list.size()-1).y;
        int w = list.size() -1;
        for(int i=w;i>=0;i--) {
            if(px == list.get(i).x && py == list.get(i).y ) {
                stack.push(i);
                px = list.get(i).prex;
                py = list.get(i).prey;
            }

            if(px == 0 && py == 0) {
                break;
            }
        }

        System.out.println("(0,0)");
        while (!stack.isEmpty()){
            System.out.println("("+list.get(stack.peek()).x+","+list.get(stack.peek()).y+")");
            stack.pop();
        }
    }

    public void depthFirst(int[][] map, int n, int m) {

        // 构建方向，向下，向右，向上，向左
        int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};
        // 标记已经走过的路
        int[][] visited = new int[n][m];
        // 保存路径
        Stack<Node> stack = new Stack<>();

        // 标记开始位置
        Node start = new Node(0,0);
        // 标记结束位置
        Node end = new Node(n-1,m-1);
        // 起始位置标记已经访问
        visited[start.x][start.y] = 1;
        // 入栈
        stack.push(start);
        // 开始走, 如果stack为空，表示没有找到路
        while (!stack.empty()) {
            // 找到路的标记
            boolean flag = false;
            // 取出前一个栈位置,不出栈
            Node now = stack.peek();
            //终点位置
            if(now.x == end.x && now.y == end.y) {
                break;
            }

            // 开始按方向走
            for(int i=0;i<dir.length;i++){
                //获取按当前位置按dir方向走的下一个位置
                Node next = new Node(now.x + dir[i][0], now.y + dir[i][1]) ;
                // 在迷宫范围内，并在迷宫内可以走，且没有走过
                if((next.x >= 0 && next.x < n) && (next.y >= 0 && next.y < m) && map[next.x][next.y] == 0 && visited[next.x][next.y] == 0){
                    // 当前位置入栈
                    stack.push(next);
                    // 标记已经访问
                    visited[next.x][next.y] = 1;
                    // 已经找到路
                    flag = true;
                    // 找到路就结束，按这个方向继续
                    break;
                }
            }
            // 找到路
            if(flag) {
                continue;
            }
            // 没找到路出栈
            Node pnode = stack.pop();
            visited[pnode.x][pnode.y] = 2;
        }

        Stack<Node> revStack = new Stack<>();
        while (!stack.isEmpty()) {
            revStack.push(stack.pop());
        }

        while (!revStack.isEmpty()) {
            Node node = revStack.pop();
            System.out.println("(" + node.x + "," + node.y + ")");
        }
    }
}

class Node {

    int x;

    int y;

    int prex;//保存前驱节点位置
    int prey;

    Node(int x, int y) {

        this.x = x;

        this.y = y;

    }
}
